package main.Q101_200;

import java.util.HashMap;
import java.util.Map;

public class Q161_170 {
    public static void main(String[] args) {
        System.out.println("Question161：");
        System.out.println("Question162：寻找峰值");
        System.out.println("Question163：");
        System.out.println("Question164：");
        System.out.println("Question165：比较版本号");
        System.out.println("Question166：分数到小数");
        System.out.println("Question167：两数之和Ⅱ-输入有序数组");
        System.out.println("Question168：Excel表列名称");
        System.out.println("Question169：多数元素");
        System.out.println("Question170：");
    }
}

class Question162{
    public static int findPeakElement(int[] nums) {
        int peakIndex=-1;
        if (nums.length==1) return 0;
        for (int i=0;i< nums.length;i++){
            if (i==0&&nums[i]>nums[i+1]) peakIndex=i;
            else if (i!=0&&i!= nums.length-1&&nums[i]>nums[i-1]&&nums[i]>nums[i+1]) peakIndex=i;
            else if (i== nums.length-1&&nums[i]>nums[i-1]) peakIndex=i;
            if (peakIndex!=-1) break;
        }
        return peakIndex;
    }
}

class Question165{
    public int compareVersion(String version1, String version2) {
        char[] str1=version1.toCharArray(),str2=version2.toCharArray();
        int i=0,j=0;
        while (i< str1.length||j< str2.length){
            int x=0;
            for (;i< str1.length&&str1[i]!='.';i++) x=x*10+str1[i]-'0';
            i++;
            int y=0;
            for (;j< str2.length&&str2[j]!='.';j++) y=y*10+str2[j]-'0';
            j++;
            if (x!=y) return x>y? 1:-1;
        }
        return 0;
    }
}

class Question166{
    public String fractionToDecimal(int numerator, int denominator) {
        long a = numerator, b = denominator;//防止溢出
        if (a % b == 0) return String.valueOf(a / b);
        StringBuilder sb = new StringBuilder();
        if (a * b < 0) sb.append('-');//判断是否存在负数
        a = Math.abs(a); b = Math.abs(b);
        sb.append(String.valueOf(a / b) + ".");
        a %= b;
        Map<Long, Integer> map = new HashMap<>();
        while (a != 0) {
            map.put(a, sb.length());// 记录当前余数所在答案的位置，并继续模拟除法运算
            a *= 10;
            sb.append(a / b);
            a %= b;
            if (map.containsKey(a)) {// 如果当前余数之前出现过，则将 [出现位置 到 当前位置] 的部分抠出来（循环小数部分）
                int u = map.get(a);
                return String.format("%s(%s)", sb.substring(0, u), sb.substring(u));
            }
        }
        return sb.toString();
    }
}

class Question167{
    public int[] twoSum(int[] numbers, int target) {
        int[] result=new int[2];
        int left=0,right= numbers.length-1;
        while (left<right){
            if (numbers[left]+numbers[right]==target){
                result[0]=left+1;
                result[1]=right+1;
                break;
            }
            if (numbers[left]+numbers[right]>target) right--;
            else if (numbers[left]+numbers[right]<target) left++;
        }
        return result;
    }
}

class Question168{
    public static String convertToTitle(int columnNumber) {
        StringBuffer result=new StringBuffer();
        while (columnNumber > 0) {
            columnNumber--;
            result.append((char)(columnNumber % 26 + 'A'));
            columnNumber /= 26;
        }
        return result.reverse().toString();
    }
}

class Question169{
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        int result=0;
        for (Integer integer:nums){
            if (!map.containsKey(integer)){//不存在则加入
                map.put(integer,1);
            }else {
                int count=map.get(integer);
                count++;
                map.put(integer,count);
            }
        }
        for (Integer integer: map.keySet()){
            if (map.get(integer)> nums.length/2) result=integer;
        }
        return result;
    }
}